\section{Explicacion del algoritmo}
La logica de la heuristica golosa sera la de reducir el 
peso total de la solucion que vayamos armando en cada paso. De 
esta manera en cada paso ire agregand un vertice a una solucion
recibida como parametro y en la cual tratare de agregar siempre
el vertice a la particion que me represente el menor costo 
en cuanto a la suma parcial que generara.\\
Luego de ubicar los $n$ vertices en la solucion,
siempre siguiendo  esta logica llegaremos a una solucion 
que se aproximara a una optima en alguna medida.\\
El problema de este tipo de aproximaciones a un problema que se resuelve de manera correcta en un 100\% con backtracking, es que al tomar una desicion solo con 
informacion local, estamos obviando el resultado que tendra
a futuro esa desicion, en el global de la solucion.\\

En nuestro caso el algoritmo posee la misma base que el algoritmo
exacto, solo que esta eliminada la posibilidad del backtracking, con 
esto el algoritmo en cada paso tomara una solucion parcial 
y con los vertices y particiones disponibles tratara
de elegir el vertice y la particion de manera tal que la suma 
generada por esta eleccion sea minima. Una vez elegido
el vertice y la parcion(puede ser una agregada al efecto), se llamara
recursivamente a la misma funcion con esta nueva sub-solucion, pero desentendiendose
del resultado final que acarreara la desicion tomada en este paso.\\
Cada nivel de recursion toma una desicion, modifica la subsolucion y retorna 
el resultado de la llamada recursiva de un nivel inferior sin hacer ningun
tipo de analisis posterior del resultado global. 

\section{Pseudocódigo}
\begin{algorithm}[H]
\KwData{GOLOSO(R,C)}
- sea R una solucion con I particiones\\
- sea C la  lista de vertices todabia no ubicados en alguna particion \\
- MinRes  mejor solucion que puedo generar hasta ahora\\
- MinV  peso de la mejor solucion hasta ahora\\
- Min\_v vertice que remuevo en la mejor solucion\\
MinV  $\leftarrow$ \infty\\
MinRes  $\leftarrow$ NULL\\
Min\_v $\leftarrow$ NULL\\

	\While{para cada v  en C}{

		C' $\leftarrow$  C  \backslash \{v\} \\

	    \IF{I $>$ 0}{\\
		    \tab\FORALL{ particion P \in  R}{\\
				\tab\tab R' $\leftarrow$   R.insert(P,v)\\ 
				\tab\tab ACTUALIZAR\_PESO(R',C')\\			    
			    \tab\tab\IF{  T$<$MinV  }{\\
				    	\tab\tab\tab   MinRes $\leftarrow$   R'\\
				    	\tab\tab\tab   MinV $\leftarrow$   T\\
				    	\tab\tab\tab   Min\_v $\leftarrow$   v\\
			    \tab\tab}
		    }
		   
		    \IF{  I$<$K  }{\\
		      	\tab  R' $\leftarrow$  \{v\} \cup R\\
		    	\tab  T $\leftarrow$ 	ACTUALIZAR\_PESO(R',C')\\	
		    	    \tab\IF{  T$<$MinV  }{\\
				    	\tab\tab   MinRes $\leftarrow$   R'\\
				    	\tab\tab   MinV $\leftarrow$   T\\
				    	\tab\tab   Min\_v $\leftarrow$   v\\
			    \tab}	 
		    	
		    }
	    }\\

	}\\
	MinV $\leftarrow$ GOLOSO(MinRes,C  \backslash \{Min\_v\})\\
	\RETURN{Minv}	
\caption{GOLOSO()}
\label{alg:ej5}
\end{algorithm}
\\
En la implementación con la técnica greedy se puede ver que primero 
se elige cual es el paso que se va  a dar y luego se llama recursivamente para
solucionar el subproblema. La decisión es tomada en base a la información
local que se obtiene al comparar todos los pasos posibles que puedo 
dar en ese instante(que vértice y donde ubicarlo). Una vez calculado el mejor paso
se toma ese camino ubicando el vértice en la partición que para el paso actual minimiza 
el aumento de peso en las particiones. 
% El pseudocodigo presentado esta simplificado ya que no  posee la poda implementada en la cual si al momento de realizar el cálculo de peso de las lineas 11 y 19 se sobrepasa el valor de $MinV$ no
% se hara la llamada recursiva a $EXACTO$. \\

% El loop de la linea 7 tratará de ubicar  cada vértice disponible
% en una partición nueva o una existente. Luego calculara como 
% eso afecta el peso de la solución llamando a $ACTUALIZAR\_PESO$ y posteriormente
% pasara el subproblema recursivamente.  Al retorno evaluara si haber 
% ubicado  $v$ en esa particion fue la decisión correcta.

% La función $ACTUALIZAR\_PESO$ es encargada de dado un vértice y una partición
% calcular cuanto incrementa el peso total de las particiones al agregarlo 
% a la partición. 


\section{Orden de complejidad}
Al eliminarse el backtracking del algoritmo, basado en el de backtracking, 
llegaremos a un orden polinomial. \\
Dada una solución recibida por parámetro, la cual posee 
$t$ particiones y  $i$ vértices disponibles para ubicar
de los $n$ totales del grafo, se tomara a cada uno de los vértices
para ubicarlos en cada una de las particiones. Aquella 
partición y vértice que representen una menor suma serán 
los elegidos para modificar la solución recibida. Esta 
operación claramente representara $t*i$ iteraciones para buscar 
vértice y partición. En el peor de los casos recorreremos 
las $K$ particiones que hay que crear y tendremos $n$ vértices. 
Adicionalmente  hay que sumar en cada partición inspeccionada
cuanto suma el vértice que se agrega. Esta operación es lineal
en función de la cantidad de vértices de la partición 
que en el peor de los casos es $n-1$.
Así para un paso $i$ del algoritmo tenemos 
$i*K*(n-i)< n*K*n = n^2*K $. Como deben ubicarse
$n$ vértices y en cada paso tenemos una complejidad de
$O(n^2*K)$ la complejidad de la aproximación golosa al problema sera $O(n^3*K)$
lo que es mucho mas eficiente que la solución factorial del algoritmo exacto.

\section{Instancias perjudiciales para la heurística}
La heurística golosa  toma las decisiones siempre teniendo 
un contexto local. Esto hace que no pueda prever que efecto tiene 
a futuro la decisión que toma. Al tratar de agregar en cada
paso el vértice que minimiza la suma total de peso en las particiones
se cae en la paradoja de producir una solución subóptima posiblemente
por haber en un paso minimizado el peso total. Si en ese paso se 
hubiera elegido otro vértice que producía un mayor incremento en la
suma de particiones por ahí en un paso posterior la suma total 
resultaría menor. \\
Un ejemplo de esto es un grafo completo de 3 vértices $A,B,C$
donde el eje  $(A, B)$  tiene peso 1 y los ejes $(B,C)$ y $(C,A)$
tiene peso 3. El algoritmo dado el objetivo de reducir en cada paso
el peso total de las particiones y como recorre siempre en un mismo 
orden los vértices, en un problema 
en el que se buscan 2 particiones para este grafo. Primero 
ubicara $A$ en una partición, decisión que minimiza el peso total 
que sera 0. En una segunda instancia ubicara a $B$ en la segunda partición 
que es lo que nuevamente minimiza el peso total que sera 0. 
En el ultimo paso deberá ubicar $C$ en alguna de las 2 particiones lo que 
hará que el peso total de las particiones sea 3. En este momento se ve que la decisión de 
minimizar el peso total en el paso anterior fue perjudicial para el resultado final. 
Si hubiera ubicado a $A$ y $B$ en la misma partición el peso total seria 1
para una solución con $A,B$ en una partición y $C$ en la otra. 



\section{Experimentación}
Nuevamente, para probar la complejidad comparamos los tiempos tomados en la corrida del algoritmo usando grafos densos y dispersos, generados aleatoriamente y limitando el valor máximo de $k$, para $k=10,50,100$. En las figuras \ref{fig:goloso:complejidadK10},\ref{fig:goloso:complejidadK50} y \ref{fig:goloso:complejidadK100} se aprecia como los grafos dispersos se procesan más rápido, por tener menos aristas, que los densos. Además en cada uno de estos gráficos vemos como la complejidad teórica depende no solo de la cantidad de nodos, eje x, sino también del valor de $k$.
\ponerGrafico{graficos/golosoK10.pdf}{Complejidad teórica y tiempo de ejecución con K$\le$10. Heurística golosa.}{1}{goloso:complejidadK10}
\ponerGrafico{graficos/golosoK50.pdf}{Complejidad teórica y tiempo de ejecución con K$\le$50. Heurística golosa.}{1}{goloso:complejidadK50}
\ponerGrafico{graficos/golosoK100.pdf}{Complejidad teórica y tiempo de ejecución con K$\le$100. Heurística golosa.}{1}{goloso:complejidadK100}